package com.gaogzhen.algorithm.recursion;

import java.util.Arrays;
import java.util.Random;

/**
 * 迷宫回溯
 * 说明:
 *  1、map表示地图
 *  2、约定：值0表示未走过；1表示墙；2表示可以走通;3已走过，但是走不通
 *  3、小球从[1][1]处出发，如果能到[8][8]位置，则说明通路找到
 *  4、策略：小球移动路线：down right up left
 */
public class MazeBacktrace {
    int[][] map = new int[10][10];
    int y = map[0].length;
    int x = map.length;

    public MazeBacktrace() {

        for (int i = 0; i< y; i++) {
            map[0][i] = 1;
            map[x-1][i] = 1;
        }
        for (int i = 0; i< x; i++) {
            map[i][0] = 1;
            map[i][y-1] = 1;
        }
    }
    public MazeBacktrace(int n) {
        this();
        for (int i = 0; i < n; i++) {
            Random r = new Random();
            int x1 = r.nextInt(x - 1);
            int y1 = r.nextInt(y - 1 );
            map[x1][y1] = 1;
        }
        map[1][1] = 0;
        map[x - 2][y - 2] = 0;
    }

    public boolean move(int xAxis, int yAxis) {
        if (map[x - 2][y - 2] == 2) {
            // 终点为2，结束
            return true;
        }
        if (map[xAxis][yAxis] == 0) {
            // 当前点为0 没走过，设置值2
            map[xAxis][yAxis] = 2;
            if (move(xAxis + 1, yAxis)) {
                // down
                return true;
            } else if (move(xAxis, yAxis + 1)) {
                // right
                return true;
            } else if (move(xAxis - 1, yAxis)) {
                // up
                return true;
            } else if (move(xAxis, yAxis - 1)) {
                // left
                return true;
            } else {
                map[xAxis][yAxis] = 3;
                return false;
            }
        }else {
            // 值1,2,3都走不通
            return false;
        }
    }

    public void show() {
        for (int[] ints : map) {
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }
    }
}
